home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part1 / 7688 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.7 KB
  1. Path: usenet.cis.ufl.edu!caen!usenet
  2. From: Tim Martin <tass@armory.com>
  3. Newsgroups: comp.lang.pascal.misc,comp.lang.c++,comp.lang.c,comp.lang.pascal.borland
  4. Subject: Re: Tough FACTORIAL math problem...
  5. Date: Sun, 25 Feb 1996 01:08:15 -0500
  6. Organization: University of Michigan Engineering, Ann Arbor
  7. Message-ID: <312FFCCF.33209502@armory.com>
  8. References: <4fr8be$ass@news.iconn.net> <4g2n5u$kqj@sun001.spd.dsccc.com> <danpop.824595562@rscernix> <4gaucn$cdu@beyond.escape.com> <4gh4cq$8eo@agate.berkeley.edu>
  9. NNTP-Posting-Host: tass@pm085-07.dialip.mich.net
  10. Mime-Version: 1.0
  11. Content-Type: text/plain; charset=us-ascii
  12. Content-Transfer-Encoding: 7bit
  13. X-Mailer: Mozilla 2.0 (X11; I; Linux 1.2.3 i486)
  14.  
  15. Bruce Kaskel wrote:
  16. > 
  17.  
  18. > So after you have finished the n-th iteration, you have multiplied your
  19. > number by n, removed the trailing zeros, and subtracted 10000 until the
  20. > number is not greater than 10000. Are you claiming that you end up with
  21. > a number with the same last digit as n! ?
  22. > 
  23. > Strictly speaking this is not correct.
  24. > 
  25. > Take the 3125-th iteration. Your algorithm yields 995.
  26. > But the rightmost non-zero digit of 3125! is not 5.
  27. > 
  28. > --Bruce Kaskel
  29.  
  30. Duh...uh..well, sorry to shoot you down but:
  31.  
  32. The original USACO problem (where this idea came from...and whoever
  33. posted it to this group needs a serious course in ethics) specified that
  34. you only needed to test up to 1000!....So, his idea works within the
  35. program specs 
  36.  
  37. BTW-I didn't enter the competition, but I also solved it that particular
  38. way...with a little more clumsy approach using strings instead of
  39. longints, but the basic concept is the same - you only need to save the
  40. last 4 non-zero digits, because you are only ever multiplying the result
  41. by something less than 1000.
  42.  
  43. Tim 
  44. tass@armory.com
  45.